Formale Sprachen

Dozent K.-J. Lange
Sprechstunde Do 13.30 - 14.30 Uhr und n.V., Raum 009, Sand 13, Tel. 29­77567
Zeit Di 16­18 und Do 16­18, Raum siehe Aushang
Umfang 4 + 2
Turnus jedes Sommersemester
Prüfungsfach Theoretische Informatik

Beschreibung:
Ein Grundelement der Theorie Formaler Sprachen ist die endliche Beschreibung potentiell unendlicher Mengen von Wörtern, sogenannten formalen Sprachen. Diese treten als formale Beschreibung von Problemen, Funktionen oder sonstiger Objekte auf. Wesentlicher Inhalt der Vorlesung sind verschiedene Grammatikmodelle sowie deren Eigenschaften hinsichtlich Beschreibungsmächtigkeit und Abschlußeigenschaften. Behandelt werden auch Beziehungen zu Automatenmodellen und damit zusammenhängend Algorithmen für die Ermittlung der Ableitbarkeit von Wörtern sowie Fragen zur Entscheidbarkeit und zur Komplexität von Problemen, die sich bei der Beschäftigung mit Grammatiken und Automaten natürlicherweise ergeben.

Voraussetzungen:
Grundstudium Informatik

Literatur:

  1. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
  2. M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978.
  3. Skript zur Vorlesung. Eine (weiter der Bearbeitung unterliegende) Version befindet sich auf den WWW-Seiten des Arbeitsbereich: http://www-fs.informatik.uni-tuebingen.de/

Bemerkungen:
Die genauen Termine und weiteren Informationen zu den Übungen werden in der ersten Vorlesungsstunde nach Rücksprache mit den Hörern gegeben.

Zurück zur Übersicht